//
//  35. 搜索插入位置.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/15.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution35 {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        // 这儿的结果的初始化也需要注意
        var result = nums.count
        while left <= right {
            let mid = (left + right) / 2
            // result 相等时即为mid
            // target 小于mid时，有可能下次不进入循环了。所以提前记录可能的结果；
            if target <= nums[mid] {
                result = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return result
    }
    
    static func test() {
        let solution = Solution35()
        let nums = [1,3,5,6]
        let result = solution.searchInsert(nums, 2)
        print(result)
    }
}
